#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=4*1e4+10;


pair<int,int> master[100];
vector<pair<int,int>> servent[100];
int n,m;
int dp[N];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int v,p,q;
		cin>>v>>p>>q;
		if(!q)
		{
			master[i]={v,v*p};
		}
		else{
			servent[q].push_back({v,p*v});
		}
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=n;j>=0;j--)
		{
			for(int k=0;k<1<<servent[i].size();k++)
			{
				int v=master[i].first,w=master[i].second;
				for(int z=0;z<servent[i].size();z++)
				{
					if(k>>z&1)
					{
						v+=servent[i][z].first;
						w+=servent[i][z].second;
					}
				}
				if(j>=v)
				{
					dp[j]=max(dp[j],dp[j-v]+w);
				}
			}
		}
	}
	
	cout<<dp[n]<<endl;
	return 0;
}
